#include <array>
#include<vector>
#include<sstream>
#include<iostream>

class Solution
{
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param b int整型vector<vector<>> 
     * @param a int整型vector<vector<>> 
     * @return int整型vector
     */
    const static int MAX = 100000;
    std::array<int, MAX> pa;
    std::array<std::array<int,12>, MAX> tree;
int cnt = 1;
    std::vector<int> countConsistentKeys(std::vector<std::vector<int>>& b,
                                         std::vector<std::vector<int>>& a)
    {
        int alen = a.size();
        std::vector<int > ans ;
        for (int i = 0; i < alen; i++)
        {
            std::stringstream ss;
            int len = a[i].size();
            for (int j = 1; j < len; j++)
            {
                ss << a[i][j] - a[i][j - 1] << "#";
            }
           // std::cout << ss.str() << std::endl;
            //insert into qianzhui tree
            insert(ss.str(  ));
        }


        int blen = b.size();
        for (int i = 0; i < blen; i++)
        {
            std::stringstream ss;
            int len = b[i].size();
            for (int j = 1; j < len; j++)
            {
                ss << b[i][j] - b[i][j - 1] << "#";
            }
            ans.push_back(count(ss.str(  )));
        }
//search qianzui tree

        return ans;
    }

    void insert (std::string s)
    {
        int index = 1;
        for (auto c: s)
        {
            int now = cal(c);
            if (tree[index][now] ==0)
            {
                tree[index][now] = ++cnt;
            }
            
            index = tree[index][now];
            if (now == 11)
            {
                pa[index]++;
            }
        }
        
    }

    int count(std::string s)
    {
        int index =1;
        for (auto c: s)
        {
            int now = cal(c);
            if (tree[index][now] ==0) return 0;
            index = tree[index][now];
        }
        return pa[index];
    }

    int cal(const char& c)
    {
        if (c=='-')
        {
            return 10;
        }else if (c=='#')
        {
            return 11;
        }else
        {
            return c-'0';
        }
        
    }
};


